package hyy_2022;

import commons.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 判断对称二叉树
 * 一个树的左子树与右子树镜像对称,说明此树是对称的
 * 什么情况下左子树与右子树互为镜像 ?
 * 1、左子树与右子树根节点具有相同的值
 * 2、每个树的右子树与另一个树的左子树镜像对称
 */
public class _0724_101_Symmetric {

    public static boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }


    /**
     *
     * 递归法
     * p、q同时指向这颗树的根节点
     * p右移,q左移
     * p左移,q右移
     * @param p
     * @param q
     * @return boolean
     */
    public static boolean check(TreeNode p, TreeNode q) {
        if(p == null && q == null) {
            return true;
        }

        if(p == null || q == null) {
            return false;
        }

        return p.val == q.val && check(p.left,q.right) && check(p.right,q.left);
    }

    /**
     * 迭代法
     * 引入队列
     * 1、初始化时,将根节点入队两次
     * 2、每次提取两个节点,比较值,队列中每连续两个节点的值应该相等
     * 3、两个节点的左右子节点按相反的顺序插入队列
     * @param u
     * @param v
     * @return boolean
     */
    public static boolean checkByIterate(TreeNode u,TreeNode v) {
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        //初始化时,根节点入队两次
        q.offer(u);
        q.offer(v);
        while(!q.isEmpty()) {
            u = q.poll();
            v = q.poll();
            if(u == null && v == null) {
                return true;
            }
            if(u == null || v == null || (u.val != v.val)) {
                return false;
            }
            q.offer(u.left);
            q.offer(v.right);
            q.offer(u.right);
            q.offer(v.left);
        }
        return true;
    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(2);
        TreeNode node4 = new TreeNode(3);
        TreeNode node5 = new TreeNode(4);
        TreeNode node6 = new TreeNode(4);
        TreeNode node7 = new TreeNode(3);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        checkByIterate(node1,node1);
    }
}
